1. Field of the Invention
The present disclosure relates to packet forwarding engines and, more particularly, to router algorithms and architectures for supporting packet filter operations.
2. Description of Related Art
Routers in a communication network, for example, a TCP/IP network, may provide a policy-based packet forwarding function where information, usually in the form of packets, is switched or routed to a further destination, e.g., along a network link. Data packets typically include, in addition to their data payload, headers that contain information about the packet itself, such as source and destination internet protocol (IP) addresses, source and destination ports, type-of-service bits, the IP next-protocol field, etc.
Packet filtering is a general mechanism by which a router or remote access server determines how to apply various policies to incoming packets. Types of policy decisions that may be applied to packets include routing decisions, priority queuing, quality of service (QoS) marking, port and address translation, dropping of unauthorized packets, etc. Policy decisions may be based on any information contained a packet header or other considerations, such as incoming or outgoing interfaces. Certain applications may also be subject to policy decisions based on the payloads, rather than the headers, of packets. For example. FTP packets could be routed based on based on input or output port numbers.
Most policy rules are applicable to a range of parameters or dimensions, such as source and destination addresses, ports, etc., rather than exact values. Policy-based routing may thus operate on any or all of a large number, n, of ranged dimensions.
Information in a policy table is typically a linear list of ranged parameters upon which a router may make policy decisions regarding the actions it will take on incoming data packets. To implement a particular policy decision, a router receives a data packet and executes a routine that uses the policy table to determine which policy to apply. Policy tables are read from the top down by a router's control mechanism. Because of this, if two or more rules may apply to a single packet but any rule in the table is not a subset of one of the other rules that applies to the packet, the table is invalid, because a packet that matches both rules will only be subject to the first rule encountered in the table.
Similarly, if some rule, A, is a subset of a more general rule, B, then the table is valid only if rule A precedes rule B in the policy table; if rule B precedes rule A, a packet that matches both rules will only be subject to rule B, preventing rule A from ever being applied to a packet.
Policy tables are typically generated offline by a router. For example, a typical enterprise gateway router includes a routing module, a network address translator, differential services, integrated services, and a firewall. Since each of these modules dumps its policy to the policy table, a table may contain hundreds or even thousands of rules for routing packets. Because a router may generate such a large number of rules, it is difficult for an administrator to determine if a particular policy table is valid. Further, routers typically do not automatically ensure that policy tables are valid. Accordingly, there is a need to easily and automatically determine whether or not a given policy table is valid, given n-ranged parameters or dimensions with which packets may be filtered.